package backtrack

// 找出所有相加之和为 n 的 k 个数的组合。
// 组合中只允许含有 1 - 9 的正整数，并且每种组合中不存在重复的数字。
// 说明：
// 所有数字都是正整数。
// 解集不能包含重复的组合。 

func combinationSum3(k int, n int) [][]int {
	var res [][]int
	backtrack(n,k,[]int{},0,1,&res)
	return res
}
// 找出和为sumTarget的k个数组合
func backtrack(sumTarget,k int, path []int, pathSum int, stratIdx int, res *[][]int) {
	if pathSum > sumTarget {
		return 
	}
	if len(path) == k && pathSum != sumTarget {
		return   // 该逻辑待优化
	}
 	if len(path) == k && pathSum == sumTarget{
		// 得到一组结果
		// 由于path是切片，传的是引用，所以需要得到值 深拷贝
		cpy := []int{}
		for _,v := range path{cpy = append(cpy, v)}
		*res = append(*res, cpy)
	}
	// 否则 此时可以进行一下剪枝
	if stratIdx > sumTarget {
		return    // 肯定超  相当于在第一次选数字时就剪枝
	}
	if stratIdx + pathSum > sumTarget {
		return 
	}
	// 9 - startIdx  + 1   可以选择的数字个数
	if 10 - stratIdx +  len(path) < k {
		// 选择不到满足长度的组合
		return   
	}
	// 暂时就想到这么多，后面再添加剪枝条件
	for i:=stratIdx;i<=9;i++{
		path = append(path, i)
		backtrack(sumTarget,k, path, pathSum+i, i+1, res)
		path = path[:len(path)-1]
	}
}